﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DK.RabbitSeries
{
    public class Fibonacci
    {

        /// <summary>
        /// 递归实现
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public static long GetToRecursion(int index) 
        {
            //结束条件
            if (index <= 1) 
            {
                return 1;
            }

            //递归
            return GetToRecursion(index - 1) + GetToRecursion(index - 2);
        }

        /// <summary>
        /// 循环实现
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public static ulong GetToFor(int index) 
        {
            ulong low = 1;
            ulong fast = 1;
            ulong all = 1;

            for (int i = 2; i <= index; ++i)
            {
                all = low + fast;
                low = fast;
                fast = all;
            }

            return all;
        }

        /// <summary>
        /// 内存指针记忆化搜索递归
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public static unsafe ulong GetToMemorryRecursion(int index) 
        {
            ulong* pArray = stackalloc ulong[index + 1];
            var temp = GetToMemorryRecursion(index, pArray);
            return temp;
        }

        protected static unsafe ulong GetToMemorryRecursion(int index,ulong* pArray) 
        {
            //结束条件
            if (index <= 1)
            {
                return 1;
            }

            //判断是否已存储过此结果
            if (*(pArray + index) != 0) 
            {
                return *(pArray + index);
            }

            //递归
            *(pArray + index) = (GetToMemorryRecursion(index - 1, pArray) + GetToMemorryRecursion(index - 2, pArray));

            //归并
            return *(pArray + index);
        }

    }
}
